package com.itzmn.newcode.offer;

import java.util.ArrayList;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/16 13:23
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 剑指Offer， 寻找二叉树路径（根节点到叶子节点）为指定的值的路径，
 *
 *  这一题，题目我没读明白，所以看了评论的做法，
 *  是求根节点到叶子节点的整个路径的值，我以为是任意两个节点的值
 *
 *   思路：
 *   遍历二叉树。遍历至叶子节点，保存一路上的节点的值，判断是否是目标值，
 *
 *          10
 *        5   12
 *      4  7
 *
 */
public class FindTreePathOfTarget {


    public static void main(String[] args) {


        int[] ints = {10,5,12,4,7};
        FindTreePathOfTarget findTreePathOfTarget = new FindTreePathOfTarget();
        TreeNode tree = findTreePathOfTarget.createTree(ints);
        findTreePathOfTarget.FindPath(tree,22);

    }


    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {

        ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();

        if (root == null){
            return paths;
        }
        find(root,target,path,paths);
        return paths;
    }

    public void find(TreeNode root,int target,ArrayList<Integer> path,ArrayList<ArrayList<Integer>> paths){

        path.add(root.val);
        //说明寻找到叶子节点，判断一路上的值是否是目标值
        if (root.left==null && root.right==null){

            if (target == root.val){
                //说明是
                paths.add(path);

                return;
            }
        }
        ArrayList<Integer> rightPath = new ArrayList<>();
        rightPath.addAll(path);
        //如果不是，继续找
        if (root.left!=null){
            find(root.left,target-root.val,path,paths);
        }
        //为什么要用rightpath重复保存一遍呢，因为，这个是深度遍历，会一直遍历到最深的叶子节点，如果现在不保存，
        //到了最深的叶子节点，path保存了一路的节点值，在回来去保存右边的，那么就会保存整棵树的值了，所以需要区分。
        if (root.right!=null){
            find(root.right,target-root.val,rightPath,paths);
        }

    }
    /**
     * 创建二叉树
     * @param arrs
     * @return
     */
    public TreeNode createTree(int[] arrs){

        ArrayList<TreeNode> treeNodes = new ArrayList<>();
        for (int i:arrs){
            treeNodes.add(new TreeNode(i));
        }
        TreeNode root = treeNodes.get(0);

        for (int i = 0; i < arrs.length/2; i++) {
            if (i*2+1<arrs.length){
                treeNodes.get(i).left=treeNodes.get(i*2+1);
            }
            if(i*2+2<treeNodes.size()){//避免偶数的时候 下标越界
                treeNodes.get(i).right=treeNodes.get(i*2+2);
            }
        }

        return root;

    }


    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
}
